package com.yx.study.leet.questionList.questions;

import org.junit.Test;

/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
 * https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
 */
public class Solution34 {
    public int[] searchRange(int[] nums, int target) {
        int left = getIndex(nums, target, true);
        int right = getIndex(nums, target, false) - 1;
        if (left <= right && right < nums.length && nums[left] == target && nums[right] == target) {
            return new int[]{left, right};
        }
        return new int[]{-1, -1};
    }

    public int getIndex(int[] nums, int target, boolean flag) {
        int left = 0, right = nums.length - 1, mid = -1, ans = nums.length; // ans默认取最大值
        while (left <= right) {
            mid = (right + left) >> 1;
            if (nums[mid] > target || (flag && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    @Test
    public void test() {
        int[] nums = new int[]{2, 2, 2, 2, 3};
        System.out.println(OutPutArray.out(searchRange(nums, 4)));
    }
}
